#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/09/24
# @Author   :Changshu
# @File     :practice_167.py
# 两数之和 II - 输入有序数组
# 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
#
# 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2

'''方法一，暴力搜索，O(n*n)，果然超出时间限制
def twoSum(numbers:list,target:int)->list:
	r=[]
	n=len(numbers)
	if n<2:
		return r
	for i in range(n):
		t=target-numbers[i]
		if t<0:
			break
		for j in range(i+1,n):
			if numbers[j]==t:
				r.append(i+1)
				r.append(j+1)
				return r
			elif numbers[j]>t:
				break
	return r
'''

'''方法二，双指针法，类似于二分查找'''
def twoSum(numbers:list,target:int)->list:
	r = []
	left,right=0,len(numbers)-1
	while left<right:
		if numbers[left]+numbers[right]==target:
			r.append(left+1)
			r.append(right+1)
			break
		elif numbers[left]+numbers[right]>target:
			right-=1
		else:
			left+=1
	return r


if __name__ == '__main__':
	numbers=[0,0,3,4]
	target=0
	r=twoSum(numbers,target)
	print(r)
